package com.lihepeng.leecode.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 堆排序 使用堆结构完成排序，一般情况下从小到大使用大碓顶，反之 使用小堆顶
 */
public class HeapSort {
    public int[] sort(int[] arrs) {
        // 首先构造大堆顶
        for (int i = arrs.length / 2 - 1; i >= 0; i--) {
            // 从第一个非叶子节点 从下到上，从右至左 开始调整结构
            adjectHeap(arrs, i, arrs.length);
        }
        for (int i = arrs.length - 1; i > 0; i--) {
            swap(arrs, 0, i);
            adjectHeap(arrs, 0, i);
        }
        return arrs;
    }

    private void swap(int[] arrs, int i, int j) {
        int temp = arrs[i];
        arrs[i] = arrs[j];
        arrs[j] = temp;
    }

    public void adjectHeap(int[] arrs, int i, int length) {
        int temp = arrs[i];
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
            if (k + 1 < length && arrs[k] < arrs[k + 1]) {
                k++;
            }
            if (arrs[k] > temp) {
                arrs[i] = arrs[k];
                i = k;
            } else {
                break;
            }
            arrs[i] = temp;
        }
    }

    public int[] topK(int[] arrs, int n) {
        int[] res = new int[n];
        // 复制k 个元素
        for (int i = 0; i < n; i++) {
            res[i] = arrs[i];
        }
        nheapSort(res);
        for (int i = n; i < arrs.length; i++) {
            if (res[0] < arrs[i]) {
                res[0] = arrs[i];
            }
            nheapSort(res);
        }
        return res;
    }

    private void nheapSort(int[] arrs) {
        // 维护一个有n元素的最小堆
        for (int i = arrs.length / 2 - 1; i >= 0; i--) {
            adjectMinHeap(arrs, i, arrs.length);
        }
        for (int i = arrs.length - 1; i > 0; i--) {
            adjectMinHeap(arrs, 0, i);
        }
    }


    private void adjectMinHeap(int[] arrs, int i, int n) {
        int temp = arrs[i];
        for (int k = i * 2 + 1; k < n; k = k * 2 + 1) {
            // 判断左右两个节点的大小关系
            if (k + 1 < arrs.length && arrs[k] > arrs[k + 1]) {
                k = k + 1;
            }
            if (arrs[k] < temp) {
                arrs[i] = arrs[k];
                i = k;
            } else {
                break;
            }
            arrs[i] = temp;
        }
    }

    /**
     * 最小堆用于从大到小 排序
     */
    public int[] heapSortRevert(int[] arrs) {
        for (int i = arrs.length / 2 - 1; i >= 0; i--) {
            buildMinHeap(arrs, 0, arrs.length);
        }
        for (int i = arrs.length; i > 0; i--) {
            buildMinHeap(arrs, 0, i);
        }
        return arrs;
    }

    /**
     * 构建最小堆
     * 从2n -1 开始 逐渐判断该节点和父节点 大小，如果小于就交换位置
     */
    public void buildMinHeap(int[] arrs, int minIndex, int maxIndex) {
        int temp = arrs[minIndex];
        for (int k = minIndex * 2 + 1; k < maxIndex; k = k * 2 + 1) {
            if (k + 1 < maxIndex && arrs[k] > arrs[k + 1]) {
                k++;
            }
            if (arrs[k] < temp) {
                arrs[minIndex] = arrs[k];
                minIndex = k;
            } else {
                break;
            }
            arrs[minIndex] = temp;
        }
    }


    @Test
    public void topKTest() {
        int[] arrs = {1, 9, 6, 7, 3, 0, 2, 4};
        int[] sort = topK(arrs, 2);
        System.out.println(Arrays.toString(sort));
    }

    @Test
    public void runTest() {
        int[] arrs = {1, 9, 6, 7, 3, 0, 2, 4};
        int[] sort = sort(arrs);
        System.out.println(Arrays.toString(sort));
    }

    @Test
    public void runTest01() {
        int[] arrs = {1, 9, 6, 7, 3, 0, 2, 4};
        int[] ints = heapSortRevert(arrs);
        System.out.println(Arrays.toString(ints));
    }


}
